CF767C Garland

首先可以确定的是,如果点权和不为3的倍数,一定不存在合法方案。

记所有点权和为sumsum

容易想到,令 dp[u]dp[u] 表示以 uu 为根的子树的点权和 , 则有转移:

dp[u]=a[u]+vsonudp[v]dp[u]=a[u]+\sum_{v \in son_u}dp[v]

然后对于点 uu , 有一个儿子 vv 使得 dp[v]=sum3dp[v]=\frac{sum}{3},那么我们可以将 vv 切开,然后 dp[u]=dp[u]dp[v]dp[u]=dp[u]-dp[v]

最后看是否有两个切点即可。

#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;

const int MAXN = 1000000;
int n , root , sum , a[ MAXN + 5 ] , dp[ MAXN + 5 ];
int v1 , v2;
vector< int > Graph[ MAXN + 5 ]; 

void dfs( int u , int fa ) {
	dp[ u ] = a[ u ];
	for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
		int v = Graph[ u ][ i ];
		if( v == fa ) continue;
		dfs( v , u ); dp[ u ] += dp[ v ]; 
		
		if( dp[ v ] == sum / 3 ) {
			if( !v1 ) v1 = v;
			else if( !v2 ) v2 = v;
			dp[ u ] -= dp[ v ];
		} 
	} 
}

int main( ) {
	scanf("%d",&n);
	for( int i = 1 , v ; i <= n ; i ++ ) {
		scanf("%d %d",&v,&a[ i ]); sum += a[ i ];
		if( !v ) root = i;
		else {
			Graph[ i ].push_back( v );
			Graph[ v ].push_back( i );
		}
	}
	if( sum % 3 ) {
		printf("-1");
		return 0;
	}
	
	dfs( root , 0 );
	if( !v1 || !v2 ) 
		printf("-1");
	else 
		printf("%d %d\n",v1,v2);
	return 0;
}